/*
 * selectK.cpp
 *
 *  Created on: Sep 12, 2012
 *      Author: jeffrey
 */

#include<iostream>
#include<stdlib.h>
#include<limits>
#include"../header/util.h"
using namespace std;
class SelectK {
public:
	static int selectK(int array[], int len, int k) {
		int s = 0, e = len - 1;
		while (s <= e) {
			int p = rand() % (e - s + 1) + s;
			int pos = partition(array, s, e, p);
			int len = pos - s + 1;
			if (len == k)
				return array[pos];
			else if (len < k) {
				s = pos + 1;
				k -= len;
			} else {
				e = pos - 1;
			}
		}
		return numeric_limits<int>::min();
	}
private:
	static int partition(int array[], int s, int e, int p) {
		int pValue = array[p];
		swap(array, p, e);
		int tmp = s;
		for (int i = s; i < e; i++)
			if (array[i] < pValue)
				swap(array, tmp++, i);
		swap(array, tmp, e);
		return tmp;
	}
	static void swap(int array[], int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

};
//int main() {
//	int array[] = { 23, 3, 5, 2, 6, 8 };
//	int len = sizeof(array) / sizeof(int);
//
//	for (int i = 0; i < len; i++) {
//		int b[] = { 23, 3, 5, 2, 6, 8 };
//		cout << SelectK::selectK(b, len, i + 1) << endl;
//	}
//
//}
